package com.chilly.linkedlist;

import java.util.ArrayList;
import java.util.List;

/**
 * 206. 反转链表
 * 单链表
 * Created by Chilly Cui on 2020/11/27.
 */
public class ReverseLinkedList {
    public static void main(String[] args) {
//        输入: 1->2->3->4->5->NULL
//        输出: 5->4->3->2->1->NULL

        ListNode listNode = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        listNode.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = null;

        new Solution().reverseList(listNode);

    }


    static class Solution {

        //递归解法


        //双指针迭代
        public ListNode reverseList(ListNode head) {
            ListNode pre = null;
            ListNode curr = head;
            ListNode tmp = null;
            while (curr != null) {
                tmp = curr.next;//记录当前节点的下一个节点
                curr.next = pre;//然后将当前节点指向pre【和后续链表断开了】
                pre = curr;
                curr = tmp;
            }
            return pre;
        }


    /*
    //利用外部空间
    public ListNode reverseList(ListNode head){
        if (head.next == null) return new ListNode(head.val);

        int[] arr = new int[100];
        int cnt = 0;

        while (head.next != null) {
            arr[cnt++] = head.val;
            head = head.next;
        }
        ListNode listNode = new ListNode(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            listNode.next = new ListNode(i);
        }
        return listNode;
    }*/
    }

    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
}
